第39章 排序算法

排序算法的作用是将一组无序的数据按照特定顺序（如升序、降序）重新排列。本章将重点介绍三种简单直观的排序算法——冒泡排序、选择排序、插入排序，以及C++标准库中sort排序函数的使用方法。

39.1 排序基本概念

1. 排序：把数据按关键字升序/降序重新排列。
2. 稳定性：排序后值相等的元素相对顺序不变则为稳定排序，反之不稳定。
3. 内部排序：全部数据加载到内存完成排序（本章算法均为内部排序）。
4. 外部排序：数据量过大，需要借助磁盘分块排序。

39.2 冒泡排序(Bubble Sort)

39.2.1 核心思想

重复遍历数组，相邻元素两两比较，逆序则交换；每轮遍历会把当前未排序区间最大值“冒泡”到末尾，末尾元素有序无需再处理；优化标记可提前终止有序数组的循环。

39.2.2 完整代码

// 升序冒泡排序
void bubbleSort(int arr[], int n){
    for(int i = 0; i < n - 1; i++){
        bool swapped = false; // 标记本轮是否发生交换
        // 末尾i个元素已有序，无需比较
        for(int j = 0; j < n - i - 1; j++){
            if(arr[j] > arr[j+1]){
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                swapped = true;
            }
        }
        if(!swapped) break; // 全程无交换，数组已有序，直接退出
    }
}

39.2.3 复杂度与特性

• 时间复杂度： 最坏(完全逆序)：$O(n^2)$ 最好(已有序)：$O(n)$ 平均：$O(n^2)$
• 空间复杂度：$O(1)$，仅用临时变量
• 稳定性：稳定（相等元素不会交换，相对位置不变）
• 适用：小规模、基本有序的数据

39.3 选择排序(Selection Sort)

39.3.1 核心思想

将数组分为已排序区、未排序区；每一轮在未排序区找到最小值，交换到未排序区首位，逐步扩大有序区间。

39.3.2 完整代码

// 升序选择排序
void selectionSort(int arr[], int n){
    for(int i = 0; i < n - 1; i++){
        int minIndex = i; // 记录未排序最小值下标
        // 遍历未排序区间找最小值
        for(int j = i + 1; j < n; j++){
            if(arr[j] < arr[minIndex]){
                minIndex = j;
            }
        }
        // 最小值与当前起始元素交换
        if(minIndex != i){
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

39.3.3 复杂度与特性

• 时间复杂度：最好/最坏/平均均为 $O(n^2)$（无论有序都要查找最小值）
• 空间复杂度：$O(1)$
• 稳定性：不稳定（相等元素可能交换位置，例[3,2,2]排序后两个2顺序颠倒）
• 特点：交换次数极少，仅每轮最多一次交换

39.4 插入排序(Insertion Sort)

39.4.1 核心思想

数组分为有序前缀、无序后缀；依次取出无序第一个元素，向前遍历有序区，把更大元素后移，空出位置插入当前元素。

39.4.2 完整代码

// 升序插入排序
void insertionSort(int arr[], int n){
    // 从第二个元素开始（第一个元素天然有序）
    for(int i = 1; i < n; i++){
        int key = arr[i]; // 待插入元素
        int j = i - 1;
        // 有序区大于key的元素全部后移
        while(j >= 0 && arr[j] > key){
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key; // 插入正确位置
    }
}

39.4.3 复杂度与特性

• 时间复杂度： 最坏(逆序)：$O(n^2)$ 最好(完全有序)：$O(n)$ 平均：$O(n^2)$
• 空间复杂度：$O(1)$
• 稳定性：稳定
• 适用：基本有序、小规模数据，常作为快排/归排底层优化子过程

39.5 C++标准库 sort 函数

39.5.1 基础语法

头文件：#include <algorithm>

// 默认升序，区间[first, last)左闭右开
sort(迭代器/数组首地址, 末尾下一地址);
// 自定义比较规则
sort(起始, 末尾, 比较函数);

39.5.2 基础数组示例

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int arr[] = {3,1,4,1,5,9};
    int len = sizeof(arr)/sizeof(arr[0]);
    // 升序排序
    sort(arr, arr + len);
    for(int x : arr) cout << x << " ";
    return 0;
}

39.3 降序实现

方式1：标准仿函数greater<int>（需<functional>）

sort(arr, arr + len, greater<int>());

方式2：自定义比较函数

bool cmp(int a, int b){
    return a > b; // a在前则为降序
}
sort(arr, arr + len, cmp);

39.4 自定义结构体排序

#include <string>
struct Student{
    string name;
    int score;
};
// 先按分数升序，同分按姓名字典序升序
bool stuCmp(const Student& s1, const Student& s2){
    if(s1.score != s2.score)
        return s1.score < s2;
    return s1.name < s2;
}
int main(){
    Student stus[] = {{"Bob",75},{"Alice",85},{"Charlie",85}};
    int cnt = sizeof(stus)/sizeof(Student);
    sort(stus, stus + cnt, stuCmp);
    return 0;
}

39.5 sort 特性

• 底层：内省排序(Introsort)，快排+堆排+插入排序混合
• 时间复杂度：平均/最坏 $O(n\log n)$
• 空间复杂度：$O(\log n)$（递归栈）
• 稳定性：不稳定；稳定排序使用stable_sort

39.6 三种简单排序对比表

排序算法	平均时间	最坏时间	最好时间	空间	稳定性	适用场景
冒泡排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	稳定	少量、基本有序数据
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定	交换操作需要尽量少的场景
插入排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	稳定	高度有序、小规模数据